package bm66;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/9/5 21:11
 * BM66. 最长公共子串
 * https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac?tpId=295&tqId=991150&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 */
public class Solution {

    // 动态规划
    public String LCS (String s1, String s2) {
        // dp[i][j] 表示 以 s1 i 结尾 s2 j 结尾所构成的子串的最大长度
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        int lastIndex = 0; // 记录最长公共子串在 s1 中的最后位置
        int maxLen = 0; // 记录最长公共子串的长度
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                    if (dp[i + 1][j + 1] > maxLen) {
                        lastIndex = i;
                        maxLen = dp[i + 1][j + 1];
                    }
                } else {
                    dp[i + 1][j + 1] = 0;
                }
            }
        }
        return s1.substring(lastIndex - maxLen + 1, lastIndex + 1);
    }
}
